#include<iostream>
#include<string>
#include<stack>
using namespace std;
//1.括号匹配问题
class Solution 
{
public:
    bool isValid(string s) 
    {
        int n = s.size();
        stack<char> st;
        bool judge = true;
        for (int i = 0; i < n; i++)
        {
            if (s[i] == '(' || s[i] == '[' || s[i] == '{')
            {
                st.push(s[i]);
            }
            else
            {
                if (st.empty())
                {
                    judge = false;
                    break;
                }
                char tmp = st.top();
                if ((tmp == '(' && s[i] == ')') ||
                    (tmp == '[' && s[i] == ']') ||
                    (tmp == '{' && s[i] == '}'))
                {
                    st.pop();
                }
                else
                {
                    judge = false;
                    break;
                }
            }
        }
        if (!st.empty())
        {
            judge = false;
        }
        return judge;
    }
};
void test()
{
    Solution s;
    string s1 = "()[]{}";
    bool tmp1 = s.isValid(s1);
    cout << tmp1 << endl;

    string s2 = "({)}";
    bool tmp2 = s.isValid(s2);
    cout << tmp2 << endl;

    string s3 = "([{}])";
    bool tmp3 = s.isValid(s3);
    cout << tmp3 << endl;
}
int main()
{
    test();
	return 0;
}